package com.tucc.hello.leetcode.no1_400.no1_200.no81_100.no95;

import com.tucc.hello.tree.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<TreeNode> treeNodeList = solution.generateTrees(8);
        treeNodeList.forEach(root -> {
            TreeNode.printPreOrder(root);
            System.out.println();
        });
        System.out.println(treeNodeList.size());
    }

    public List<TreeNode> generateTrees(int n) {
        List<Integer> member = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            member.add(i + 1);
        }
        return generateTrees(member);
    }

    public List<TreeNode> generateTrees(List<Integer> member) {
        List<TreeNode> result = new ArrayList<>();
        if (member.size() == 0) {
            result.add(null);
            return result;
        }
        if (member.size() == 1) {
            TreeNode treeNode = new TreeNode(member.get(0));
            result.add(treeNode);
            return result;
        }
        for (int i = 0; i < member.size(); i++) {
            int rootVal = member.get(i);
            List<Integer> left = new ArrayList<>();
            List<Integer> right = new ArrayList<>();
            for (int j = 0; j < member.size(); j++) {
                if (i != j) {
                    if (member.get(j) > rootVal) {
                        right.add(member.get(j));
                    } else {
                        left.add(member.get(j));
                    }
                }
            }
            List<TreeNode> leftList = generateTrees(left);
            List<TreeNode> rightList = generateTrees(right);
            for (int m = 0; m < leftList.size(); m++) {
                for (int n = 0; n < rightList.size(); n++) {
                    TreeNode root = new TreeNode(rootVal);
                    root.left = leftList.get(m);
                    root.right = rightList.get(n);
                    result.add(root);
                }
            }
        }
        return result;
    }

}
